package com.gitee.wsl.collections.map

import com.gitee.wsl.collections.bean.HashEntry
import com.gitee.wsl.collections.iterator.EmptyMutableIterator
import com.gitee.wsl.collections.iterator.api.MutableMapEntry
import com.gitee.wsl.collections.iterator.api.OrderedIterator
import com.gitee.wsl.collections.iterator.api.OrderedMapIterator
import com.gitee.wsl.collections.iterator.api.ResettableIterator
import com.gitee.wsl.collections.map.api.OrderedMap
import kotlin.jvm.Transient


/**
 * An abstract implementation of a hash-based map that links entries to create an
 * ordered map and which provides numerous points for subclasses to override.
 *
 *
 * This class implements all the features necessary for a subclass linked
 * hash-based map. Key-value entries are stored in instances of the
 * `LinkEntry` class which can be overridden and replaced.
 * The iterators can similarly be replaced, without the need to replace the KeySet,
 * EntrySet and Values view classes.
 *
 *
 *
 * Overridable methods are provided to change the default hashing behavior, and
 * to change how entries are added to and removed from the map. Hopefully, all you
 * need for unusual subclasses is here.
 *
 *
 *
 * This implementation maintains order by original insertion, but subclasses
 * may work differently. The `OrderedMap` interface is implemented
 * to provide access to bidirectional iteration and extra convenience methods.
 *
 *
 *
 * The `orderedMapIterator()` method provides direct access to a
 * bidirectional iterator. The iterators from the other views can also be cast
 * to `OrderedIterator` if required.
 *
 *
 *
 * All the available iterators can be reset back to the start by casting to
 * `ResettableIterator` and calling `reset()`.
 *
 *
 *
 * The implementation is also designed to be subclassed, with lots of useful
 * methods exposed.
 *
 *
 * @param <K> the type of the keys in this map
 * @param <V> the type of the values in this map
 * @since 3.0
</V></K> */
abstract class AbstractLinkedMap<K, V> : AbstractHashedMap<K?, V?>, OrderedMap<K?, V?> {
    /**
     * EntrySet iterator.
     *
     * @param <K> the key type.
     * @param <V> the value type.
    </V></K> */
    protected class EntrySetIterator<K, V> protected constructor(
        parent: AbstractLinkedMap<K,V>
    ) : LinkIterator<K,V>(parent), OrderedIterator<LinkEntry<K,V>>, ResettableIterator<LinkEntry<K,V>> {
         override fun next(): LinkEntry<K,V> {
            return super.nextEntry()!!
        }

        override fun previous(): LinkEntry<K,V> {
            return super.previousEntry()!!
        }
    }

    /**
     * KeySet iterator.
     *
     * @param <K> the key type.
    </K> */
    protected class KeySetIterator<K,V> protected constructor(
        parent: AbstractLinkedMap<K,V>
    ) : LinkIterator<K,V>(parent), OrderedIterator<K?>, ResettableIterator<K?> {
         override fun next(): K? {
            return super.nextEntry()!!.key
        }

        override fun previous(): K? {
            return super.previousEntry()!!.key
        }
    }

    /**
     * LinkEntry that stores the data.
     *
     *
     * If you subclass `AbstractLinkedMap` but not `LinkEntry`
     * then you will not be able to access the protected fields.
     * The `entryXxx()` methods on `AbstractLinkedMap` exist
     * to provide the necessary access.
     *
     *
     * @param <K> the key type.
     * @param <V> the value type.
    </V></K> */
    open class LinkEntry<K, V>: HashEntry<K?,V?>{

       constructor(key: K?, value: V?,
                   hashCode: Int = key.hashCode() + value.hashCode(),
                   next: HashEntry<K?, V?>? = null
       ):super(key,value,hashCode,next)

        /** The entry before this one in the order  */
        var before: LinkEntry<K,V>? = null

        /** The entry after this one in the order  */
        var after: LinkEntry<K,V>? = null

        companion object{

        }
    }

    /**
     * Base Iterator that iterates in link order.
     *
     * @param <K> the key type.
     * @param <V> the value type.
    </V></K> */
    protected abstract class LinkIterator<K, V> protected constructor(
        /** The parent map  */
        protected val parent: AbstractLinkedMap<K, V>
    ) {

        /** The current (last returned) entry  */
        protected var last: LinkEntry<K,V>? = null

        /** The next entry  */
        protected var next: LinkEntry<K,V>? = parent.header.after

        /** The modification count expected  */
        protected var expectedModCount: Int = parent.modCount

        /**
         * Constructs a new instance.
         *
         * @param parent The parent AbstractLinkedMap.
         */
        //init {
            //this.next = parent.header.after
            //this.expectedModCount = parent.modCount
        //}

        /**
         * Gets the current entry.
         *
         * @return the current entry.
         */
        protected fun currentEntry(): LinkEntry<K,V>? {
            return last
        }

        /**
         * Tests whether there is another entry.
         *
         * @return whether there is another entry.
         */
        fun hasNext(): Boolean {
            return next != parent.header
        }

        /**
         * Tests whether there is a previous entry.
         *
         * @return whether there is a previous entry.
         */
        fun hasPrevious(): Boolean {
            return next?.before != parent.header
        }

        /**
         * Gets the next entry.
         *
         * @return the next entry.
         */
        protected fun nextEntry(): LinkEntry<K,V>? {
            if (parent.modCount != expectedModCount) {
                throw ConcurrentModificationException()
            }
            if (next === parent.header) {
                throw NoSuchElementException(NO_NEXT_ENTRY)
            }
            last = next
            next = next?.after
            return last
        }

        /**
         * Gets the previous entry.
         *
         * @return the previous entry.
         */
        protected fun previousEntry(): LinkEntry<K,V>? {
            if (parent.modCount != expectedModCount) {
                throw ConcurrentModificationException()
            }
            val previous = next?.before
            if (previous === parent.header) {
                throw NoSuchElementException(NO_PREVIOUS_ENTRY)
            }
            next = previous
            last = previous
            return last
        }

        /**
         * Removes the current entry.
         */
        fun remove() {
            checkNotNull(last) { REMOVE_INVALID }
            if (parent.modCount != expectedModCount) {
                throw ConcurrentModificationException()
            }
            parent.remove(last!!.key)
            last = null
            expectedModCount = parent.modCount
        }

        /**
         * Resets the state to the end.
         */
        fun reset() {
            last = null
            next = parent.header.after
        }

        override fun toString(): String {
            if (last != null) {
                return "Iterator[" + last!!.key + "=" + last!!.value + "]"
            }
            return "Iterator[]"
        }
    }

    /**
     * MapIterator implementation.
     *
     * @param <K> the key type.
     * @param <V> the value type.
    </V></K> */
    protected class LinkMapIterator<K, V> (
        parent: AbstractLinkedMap<K,V>
    ) : LinkIterator<K,V>(parent), OrderedMapIterator<K?,V?>, ResettableIterator<K?> {
        override fun getKey(): K? {
            val current = currentEntry()
            checkNotNull(current) { GETKEY_INVALID }
            return current.key
        }

        override fun getValue(): V? {
            val current = currentEntry()
            checkNotNull(current) { GETVALUE_INVALID }
            return current.value
        }

        override fun next(): K? {
            return super.nextEntry()!!.key
        }

        override fun previous(): K? {
            return super.previousEntry()!!.key
        }

        override fun setValue(value: V?): V? {
            val current = currentEntry()
            checkNotNull(current) { SETVALUE_INVALID }
            return current.setValue(value)
        }
    }

    /**
     * Values iterator.
     *
     * @param <V> the value type.
    </V> */
    protected class ValuesIterator<K,V> protected constructor(
        parent: AbstractLinkedMap<K,V>
    ) : LinkIterator<K,V>(parent), OrderedIterator<V?>, ResettableIterator<V?> {
        override fun next(): V? {
            return super.nextEntry()!!.value
        }

        override fun previous(): V? {
            return super.previousEntry()!!.value
        }
    }

    /** Header in the linked list  */
    @Transient
    lateinit var header: LinkEntry<K,V>

    /**
     * Constructor only used in deserialization, do not use otherwise.
     */
    protected constructor()

    /**
     * Constructs a new, empty map with the specified initial capacity.
     *
     * @param initialCapacity  the initial capacity
     * @throws IllegalArgumentException if the initial capacity is negative
     */
    protected constructor(initialCapacity: Int) : super(initialCapacity)

    /**
     * Constructs a new, empty map with the specified initial capacity and
     * load factor.
     *
     * @param initialCapacity  the initial capacity
     * @param loadFactor  the load factor
     * @throws IllegalArgumentException if the initial capacity is negative
     * @throws IllegalArgumentException if the load factor is less than zero
     */
    protected constructor(initialCapacity: Int, loadFactor: Float) : super(initialCapacity, loadFactor)

    /**
     * Constructor which performs no validation on the passed in parameters.
     *
     * @param initialCapacity  the initial capacity, must be a power of two
     * @param loadFactor  the load factor, must be &gt; 0.0f and generally &lt; 1.0f
     * @param threshold  the threshold, must be sensible
     */
    protected constructor(initialCapacity: Int, loadFactor: Float, threshold: Int) : super(
        initialCapacity,
        loadFactor,
        threshold
    )

    /**
     * Constructor copying elements from another map.
     *
     * @param map  the map to copy
     * @throws NullPointerException if the map is null
     */
    protected constructor(map: Map<K?,V?>) : super(map)

    /**
     * Adds an entry into this map, maintaining insertion order.
     *
     *
     * This implementation adds the entry to the data storage table and
     * to the end of the linked list.
     *
     *
     * @param entry  the entry to add
     * @param hashIndex  the index into the data array to store at
     */
    override fun addEntry(entry: HashEntry<K?,V?>, hashIndex: Int) {
        val link = entry as LinkEntry<K,V>
        link.after = header
        link.before = header.before
        header.before!!.after = link
        header.before = link
        data[hashIndex] = link
    }

    /**
     * Clears the map, resetting the size to zero and nullifying references
     * to avoid garbage collection issues.
     */
     override fun clear() {
        // override to reset the linked list
        super.clear()
        header.after = header
        header.before = header.after
    }

    override fun destroyEntry(entry: HashEntry<K?,V?>) {
        entry.next = null
        entry.key = null
        entry.value = null
    }

    /**
     * Checks whether the map contains the specified value.
     *
     * @param value  the value to search for
     * @return true if the map contains the value
     */
     override fun containsValue(value: V?): Boolean {
        // override uses faster iterator
        if (value == null) {
            var entry = header.after
            while (entry != header) {
                if (entry!!.value == null) {
                    return true
                }
                entry = entry.after
            }
        } else {
            var entry = header.after
            while (entry != header) {
                if (isEqualValue(value, entry!!.value)) {
                    return true
                }
                entry = entry.after
            }
        }
        return false
    }

    /**
     * Creates an entry to store the data.
     *
     *
     * This implementation creates a new LinkEntry instance.
     *
     *
     * @param next  the next entry in sequence
     * @param hashCode  the hash code to use
     * @param key  the key to store
     * @param value  the value to store
     * @return the newly created entry
     */
    override fun createEntry(next: HashEntry<K?,V?>?, hashCode: Int, key: K?, value: V?): LinkEntry<K,V> {
        return LinkEntry( convertKey(key), value, hashCode,next)
    }

    /**
     * Creates an entry set iterator.
     * Subclasses can override this to return iterators with different properties.
     *
     * @return the entrySet iterator
     */
    override fun createEntrySetIterator(): MutableIterator<MutableMapEntry<K?, V?>> {
        if (isEmpty()) {
            return EmptyMutableIterator
        }
        return EntrySetIterator(this)
    }

    /**
     * Creates a key set iterator.
     * Subclasses can override this to return iterators with different properties.
     *
     * @return the keySet iterator
     */
    override fun createKeySetIterator(): MutableIterator<K?> {
        if (isEmpty()) {
            return EmptyMutableIterator
        }
        return KeySetIterator(this)
    }

    /**
     * Creates a values iterator.
     * Subclasses can override this to return iterators with different properties.
     *
     * @return the values iterator
     */
    override fun createValuesIterator(): MutableIterator<V?> {
        if (isEmpty()) {
            return EmptyMutableIterator
        }
        return ValuesIterator(this)
    }

    /**
     * Gets the `after` field from a `LinkEntry`.
     * Used in subclasses that have no visibility of the field.
     *
     * @param entry  the entry to query, must not be null
     * @return the `after` field of the entry
     * @throws NullPointerException if the entry is null
     * @since 3.1
     */
    protected fun entryAfter(entry: LinkEntry<K,V>): LinkEntry<K,V>? {
        return entry.after
    }

    /**
     * Gets the `before` field from a `LinkEntry`.
     * Used in subclasses that have no visibility of the field.
     *
     * @param entry  the entry to query, must not be null
     * @return the `before` field of the entry
     * @throws NullPointerException if the entry is null
     * @since 3.1
     */
    protected fun entryBefore(entry: LinkEntry<K,V>): LinkEntry<K,V>? {
        return entry.before
    }

    /**
     * Gets the first key in the map, which is the first inserted.
     *
     * @return the eldest key
     */
    override fun firstKey(): K? {
        if (isEmpty()) {
            throw NoSuchElementException("Map is empty")
        }
        return header.after!!.key
    }

    /**
     * Gets the key at the specified index.
     *
     * @param index  the index to retrieve
     * @return the key at the specified index
     * @throws IndexOutOfBoundsException if the index is invalid
     */
    protected fun getEntry(index: Int): LinkEntry<K,V>? {
        if (index < 0) {
            throw IndexOutOfBoundsException("Index $index is less than zero")
        }
        if (index >= size) {
            throw IndexOutOfBoundsException("Index $index is invalid for size $size")
        }
        var entry: LinkEntry<K,V>?
        if (index < size / 2) {
            // Search forwards
            entry = header.after
            for (currentIndex in 0..<index) {
                entry = entry?.after
            }
        } else {
            // Search backwards
            entry = header
            for (currentIndex in size downTo index + 1) {
                entry = entry?.before
            }
        }
        return entry
    }

    override fun getEntry(key: K?): LinkEntry<K,V>? {
        return super.getEntry(key) as LinkEntry<K,V>?
    }

    /**
     * Initialize this subclass during construction.
     *
     *
     * Note: As from v3.2 this method calls
     * [.createEntry] to create
     * the map entry object.
     *
     */
    override fun init() {
        header = createEntry(null, -1, null, null)
        header.after = header
        header.before = header.after
    }

    /**
     * Gets the last key in the map, which is the most recently inserted.
     *
     * @return the most recently inserted key
     */
    override fun lastKey(): K? {
        if (isEmpty()) {
            throw NoSuchElementException("Map is empty")
        }
        return header.before!!.key
    }

    /**
     * {@inheritDoc}
     */
    override fun mapIterator(): OrderedMapIterator<K?,V?> {
//        if (isEmpty()) {
//            return EmptyOrderedMapIterator
//        }
        return LinkMapIterator(this)
    }

    /**
     * Gets the next key in sequence.
     *
     * @param key  the key to get after
     * @return the next key
     */
    override fun nextKey(key: K?): K? {
        val entry = getEntry(key)
        return if (entry == null || entry.after === header) null else entry.after!!.key
    }

    /**
     * Gets the previous key in sequence.
     *
     * @param key  the key to get before
     * @return the previous key
     */
    override fun previousKey(key: K?): K? {
        val entry = getEntry(key)
        return if (entry == null || entry.before === header) null else entry.before!!.key
    }

    /**
     * Removes an entry from the map and the linked list.
     *
     *
     * This implementation removes the entry from the linked list chain, then
     * calls the superclass implementation.
     *
     *
     * @param entry  the entry to remove
     * @param hashIndex  the index into the data structure
     * @param previous  the previous entry in the chain
     */
    override fun removeEntry(entry: HashEntry<K?,V?>, hashIndex: Int, previous: HashEntry<K?,V?>?) {
        val link = entry as LinkEntry<K,V>
        link.before!!.after = link.after
        link.after!!.before = link.before
        link.after = null
        link.before = null
        super.removeEntry(entry, hashIndex, previous)
    }

}
